package offer;

import java.util.ArrayDeque;
import java.util.Deque;

public class _13_机器人的运动范围 {
    public static void main(String[] args) {
        int m = 14;
        int n = 14;
        int k = 1;
        Solution solution = new _13_机器人的运动范围().new Solution();
        System.out.println(solution.movingCount(m, n, k));
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                System.out.print(solution.shuWeiHe(i) + solution.shuWeiHe(j) <= k ? "T " : "F ");
//            }
//            System.out.println();
//        }
    }

    // 广度优先遍历
    class Solution3 {

        public int movingCount(int m, int n, int k) {
            if (k == 0) {
                return 1;
            }
            Deque<int[]> queue = new ArrayDeque<>();
            boolean[][] vis = new boolean[m][n];
            queue.addLast(new int[] {0, 0});
            int[] dx = {0, 1};
            int[] dy = {1, 0};
            vis[0][0] = true;
            int res = 1;
            while (!queue.isEmpty()) {
                int[] cell = queue.pollFirst();
                int x = cell[0];
                int y = cell[1];
                for (int i = 0; i < 2; i++) {
                    int tx = dx[i] + x;
                    int ty = dy[i] + y;
                    if (tx < 0 || tx >= m || ty < 0 || ty >= n || vis[tx][ty] || shuWeiHe(tx) + shuWeiHe(ty) > k) {
                        continue;
                    }
                    queue.addLast(new int[] {tx, ty});
                    vis[tx][ty] = true;
                    res++;
                }
            }
            return res;
        }

        private int shuWeiHe(int num) {
            int sum = 0;
            while(num != 0) {
                sum += num % 10;
                num /= 10;
            }
            return sum;
        }
    }


    // 进行了一定的优化，深度优先遍历的最优方法
    class Solution {
        boolean[][] visited;

        public int movingCount(int m, int n, int k) {
            visited = new boolean[m][n];
            return dfs(m, n, 0, 0, k);
        }
        private int dfs(int m, int n, int i, int j, int k) {
            if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || shuWeiHe(i) + shuWeiHe(j) > k) {
                return 0;
            }
            visited[i][j] = true;
            return 1 + dfs(m, n, i + 1, j, k) + dfs(m, n, i, j + 1, k);
        }

        private int shuWeiHe(int num) {
            int sum = 0;
            while(num != 0) {
                sum += num % 10;
                num /= 10;
            }
            return sum;
        }
    }

    // 已经跑通了，可以优化
    class Solution2 {
        boolean[][] visited;

        public int movingCount(int m, int n, int k) {
            visited = new boolean[m][n];
            return dfs(m, n, 0, 0, k);
        }
        private int dfs(int m, int n, int i, int j, int k) {
            if (i < 0 || i >= m || j < 0 || j >= n) {
                return 0;
            }
            if (visited[i][j ]) {
                return 0;
            } else {
                if (shuWeiHe(i) + shuWeiHe(j) <= k) {
                    visited[i][j] = true;
                    int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
                    int sum = 1;
                    for (int[] direction : directions) {
                        int newi = i + direction[0];
                        int newj = j + direction[1];
                        sum += dfs(m, n, newi, newj, k);
                    }
                    return sum;
                } else {
                    return 0;
                }
            }
        }

        private int shuWeiHe(int num) {
            int sum = 0;
            while(num != 0) {
                sum += num % 10;
                num /= 10;
            }
            return sum;
        }
    }

    //这个解法没有考虑能不能走到，只考虑了每个格子是否符合要求
    class Solution1 {
        public int movingCount(int m, int n, int k) {
            int count = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (shuWeiHe(i) + shuWeiHe(j) <= k) {
                        count++;
                    }
                }
            }
            return count;
        }

        private int shuWeiHe(int num) {
            int sum = 0;
            while(num != 0) {
                sum += num % 10;
                num /= 10;
            }
            return sum;
        }
    }
}
